package com.chj.jz.dp.class03;

public class Code01_PaintHouseII {
	/**
	 * @param costs:
	 *            n x k cost matrix
	 * @return: an integer, the minimum cost to paint all houses
	 */
	public static int minCostII(int[][] costs) {
		// write your code here
		int n = costs.length;
		if (n == 0) {
			return 0;
		}

		int K = costs[0].length;
		int[][] f = new int[n + 1][K];
		int i, j;
		int min1, min2;
		int id1 = 0;
		int id2 = 0;

		for (i = 0; i < K; i++) {
			f[0][i] = 0;
		}

		for (i = 1; i <= n; i++) {
			min1 = Integer.MAX_VALUE;
			min2 = Integer.MAX_VALUE;

			for (j = 0; j < K; j++) {
				if (f[i - 1][j] < min1) {
					min2 = min1;
					id2 = id1;
					min1 = f[i - 1][j];
					id1 = j;

				} else if (f[i - 1][j] < min2) {
					min2 = f[i - 1][j];
					id2 = j;
				}
			}

			for (j = 0; j < K; j++) {
				f[i][j] = costs[i - 1][j];
				if (j != id1) {
					f[i][j] += min1;

				} else {
					f[i][j] += min2;
				}
			}
		}

		int res = Integer.MAX_VALUE;
		for (i = 0; i < K; i++) {
			res = Math.min(res, f[n][i]);
		}
		return res;
	}

	public static void main(String[] args) {
		{
			int[][] arr = new int[][] { { 14, 2, 11 }, { 11, 14, 5 }, { 14, 3, 10 } };
			System.out.println(minCostII(arr));
		}
		{
			int[][] arr = new int[][] { { 1, 2, 3 }, { 1, 4, 6 } };
			System.out.println(minCostII(arr));
		}
		{
			int[][] arr = new int[][] { { 5 } };
			System.out.println(minCostII(arr));
		}
	}

}
